package LeetCode.leetcode739;

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
//    /**
//     * 暴力解法
//     * @param temperatures
//     * @return
//     */
//    public int[] dailyTemperatures(int[] temperatures) {
//        int[] result = new int[temperatures.length];
//        for (int i = 0; i < temperatures.length; i++) {
//            int j = i + 1;
//            for (; j < temperatures.length; j++) {
//                if (temperatures[j] > temperatures[i]) {
//                    result[i] = j - i;
//                    break;
//                }
//            }
//            if (j == temperatures.length) {
//                result[i] = 0;
//            }
//        }
//        return result;
//
//    }
    public int[] dailyTemperatures(int[] temperatures) {
        Deque<Integer> stack = new ArrayDeque<>();
        int[] res = new int[temperatures.length];
        for (int i = 0; i < temperatures.length; i++) {
            int cur = temperatures[i];
            while (!stack.isEmpty() && temperatures[stack.peek()] < cur) {
                res[stack.peek()] = i - stack.peek();
                stack.pop();
            }
            stack.push(i);
        }
        return res;
    }
}